Quasi Monte Carlo Integration

Note. I denote the modulo operation with $[\dummyarg]_n$. In particular $[\dummyarg]_1$ is the fractional part.

$$ \mod{a}_b ≜ a - b ⋅ \floor{\frac a b} $$

Roberts sequence

Definition. The $d$-dimensional Roberts sequence is a particularly elegant low-discrepancy sequence:

$$ \begin{aligned} \vec x_i &≜ \mod{i ⋅ \vec ϕ_d}_1 & \vec ϕ_d &≜ \begin{bmatrix} ϕ_d \\\\ ϕ_d^2 \\\\ \vdots \\\\ ϕ_d^d \end{bmatrix} \end{aligned} $$

where $ϕ_d$ is the unique positive root of $x^{d+1} + x^d - 1$ and $\mod{\dummyarg}_1$ is taken element wise over vectors.

Note. The root will be in $(\frac 12, 1)$. Closed form solutions for $ϕ_1$ and $ϕ_2$ are the reciprocals of the golden ratio and the plastic number:

$$ \begin{aligned} ϕ_1 &= \frac{\sqrt{5} - 1}{2} & ϕ_2 &= \sqrt[3]{\frac{25 + \sqrt{207}}{54}} + \sqrt[3]{\frac{25 - \sqrt{207}}{54}} -\frac 1 3 \end{aligned} $$

Note. In Roberts' notes the $ϕ_d$ is defined in reciprocal form compared to here. These definitions are algebraically identical.

To do. A procedure to compute the nearest odd number $k$ to $ϕ_d^j ⋅ 2^{64}$, this number will iterate through all $2^{64}$ numbers and can be implemented with a single overflowing multiplication or iterated addition:

$$ \begin{aligned} n_i &= \mod{i ⋅ k}\_{2^{64}} & n_{i + 1} &= \mod{n_i + k}_{2^{64}} \end{aligned} $$

To do

Does this work for rendering too?

https://www.cs.cmu.edu/~kmcrane/Projects/MonteCarloGeometryProcessing/paper.pdf

References

http://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/

https://news.ycombinator.com/item?id=17873284

https://statweb.stanford.edu/~owen/mc/Ch-quadrature.pdf

https://statweb.stanford.edu/~owen/mc/